﻿using Microsoft.VisualStudio.GraphModel;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Timtopia.DGMLPosterView
{
    public class ShortestPaths
    {
        public static int[,] FloydWarshall(Graph graph, out List<GraphNode> V) 
        {
            int[,] dist;
            V = graph.Nodes.Where(v => !v.IsGroup).ToList();
            var E = graph.Links.Where(e => !e.HasCategory(GraphCommonSchema.Contains) && !e.IsPseudo);
            int n = V.Count;
            dist = new int[n, n];
            var nodeIndexes = new Dictionary<GraphNode, int>();
            for (int i = 0; i < n; ++i)
            {
                nodeIndexes[V[i]] = i;
                for (int j = 0; j < n; ++j)
                    dist[i, j] = i==j ? 0 : -1;
            }
            foreach (var e in E)
            {
                int u = nodeIndexes[e.Source];
                int v = nodeIndexes[e.Target];
                dist[u, v] = 1;
            }
            for (int k = 0; k < n; ++k)
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j)
                    {
                        int dik = dist[i, k];
                        int dkj = dist[k, j], dij = dist[i,j];
                        int dikj = dik + dkj;
                        dist[i, j] = dik < 0 || dkj < 0 ? dij : (dij < 0 ? dikj : Math.Min(dij, dikj));
                    }
                }
            return dist;
        }

        private enum color { GREY, BLACK };

        /// <summary>
        /// Traverse BFS from s to t.  Return the length l of the shortest path.
        /// Put all the links involved in a path with \le l links from s to t.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="e"></param>
        /// <param name="paths"></param>
        /// <returns></returns>
        public static int FromTo(GraphNode s, GraphNode t, out List<GraphLink> paths)
        {
            var q = new Queue<GraphNode>();
            paths = new List<GraphLink>();
            q.Enqueue(s);
            var visited = new HashSet<GraphNode>();
            visited.Add(s);
            var pred = new Dictionary<GraphNode, List<GraphLink>>();
            pred[s] = new List<GraphLink>();
            var d = new Dictionary<GraphNode, int>();
            d[s] = 0;
            while (q.Any())
            {
                var u = q.Dequeue();
                foreach (var l in u.OutgoingLinks)
                {
                    var v = l.Target;
                    if (!visited.Contains(v))
                    {
                        visited.Add(v);
                        d[v] = d[u] + 1;
                        q.Enqueue(v);
                    }
                    if (d[v] == d[u] + 1) {
                        List<GraphLink> incoming;
                        if (!pred.TryGetValue(v, out incoming))
                        {
                            incoming = new List<GraphLink>();
                            pred[v] = incoming;
                        }
                        incoming.Add(l);
                    }
                }
            }
            q.Clear();
            q.Enqueue(t);
            while (q.Any())
            {
                var v = q.Dequeue();
                foreach (var l in pred[v])
                {
                    q.Enqueue(l.Source);
                    paths.Add(l);
                }
            }
            return d[t];
        }
    }
}
